import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class Solution380 {

    Map<Integer, Integer> invertIndex;

    List<Integer> dataSet;

    Random random;

    public Solution380() {
        this.invertIndex = new HashMap<>();
        this.dataSet = new ArrayList<>();
        this.random = new Random();
    }

    public boolean insert(int val) {
        if(invertIndex.containsKey(val)){
            return false;
        }
        int valInd = dataSet.size();
        dataSet.add(val);
        invertIndex.put(val, valInd);
        return true;
    }

    public boolean remove(int val) {
        if(invertIndex.containsKey(val)){
            int valInd = invertIndex.remove(val);
            int lastVal = dataSet.remove(dataSet.size() - 1);
            if(val != lastVal) {
                dataSet.set(valInd, lastVal);
                invertIndex.put(lastVal, valInd);
            }
            return true;
        }
        return false;
    }

    public int getRandom() {
        int ind = random.nextInt(dataSet.size());
        return dataSet.get(ind);
    }
}
